import math
from typing import List 
def largestNumber(nums) -> str:
    n=len(nums)
    nums=list(map(str,nums))
    for i in range(n):
        for j in range(i+1,n):
            if nums[i]+nums[j]<nums[j]+nums[i]:
                nums[i],nums[j]=nums[j],nums[i]
        
    return str(int("".join(nums)))

def largestNumber_y(nums) -> str:
    def fun(x):
        if x==0:return 0
        L=int(math.log10(x))+1
        return x/(10**L-1)
    nums.sort(key=fun,reverse=True)
    nums=list(map(str,nums))
    return str(int("".join(nums)))

def permute(nums) -> List[List[int]]:
    res = []
    def backtrack(nums, tmp):
        if not nums:
            res.append(tmp)
            return 
        for i in range(len(nums)):
            backtrack(nums[:i] + nums[i+1:], tmp + [nums[i]])
    backtrack(nums, [])
    return res


def lengthOfLIS(nums) -> int:
    if not nums:
        return 0
    dp = []
    for i in range(len(nums)):
        dp.append(1)
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)